package com.leetcode.algorithm.y22.m09.w2;

import java.util.Arrays;

/**
 * 452. 用最少数量的箭引爆气球
 * 
 * https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
 * 
 * @author jie.deng
 *
 */
class Question0452Solution01 {

	public int findMinArrowShots(int[][] points) {
		// 按照左边界进行排序后，如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭
		// 局部最优：当气球出现重叠，一起射，所用弓箭最少。
		// 全局最优：把所有气球射爆所用弓箭最少。
		int len = points.length;
		Arrays.sort(points, (arr1, arr2) -> Integer.compare(arr1[0], arr2[0]));
		int cnt = 1;
		int arrowX = points[0][1];
		for (int idx = 1; idx < len; idx++) {
			if (points[idx][0] > arrowX) {
				cnt++;
				arrowX = points[idx][1];
			} else {
				if (points[idx][1] < arrowX) {
					arrowX = points[idx][1];
				}
			}
		}
		return cnt;
	}

}